package leetcode.dynamic;

/*

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

 

示例 1：


输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：


输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：

输入：matrix = [["0"]]
输出：0
 

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'
通过次数127,881提交次数271,583

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 */

public class LeetCode221_MaximalSquare {

    public int maximalSquare(char[][] matrix) {

        int max = 0;
        int tempMax;
        for (int i = 0; i < matrix.length; i++){
            for (int j = 0; j < matrix[0].length; j++){
                if (matrix[i][j] == '1'){
                    tempMax = square(i, j, matrix);
                    if (tempMax > max){
                        max = tempMax;
                    }
                }
            }
        }
        return max;
    }

    public int square(int i, int j, char[][] matrix){

        int s = 1;

        int p = i + 1;
        int q = j + 1;

        int tempP, tempQ;
        boolean done = false;

        while (p < matrix.length && q < matrix[0].length){
            tempP = i;
            while (tempP <= p){
                if (matrix[tempP][q] == '1'){
                    tempP++;
                }else {
                    done = true;
                    break;
                }
            }
            if (done){
                break;
            }
            tempQ = q;
            while (tempQ >= j){
                if (matrix[p][tempQ] == '1'){
                    tempQ--;
                }else {
                    done = true;
                    break;
                }
            }

            if (done){
                break;
            }

            s++;
            p++;
            q++;

        }
        return s * s;

    }

    public static void main(String[] args) {
//        char[][] matrix = {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};
        char[][] matrix = {{'1','1','1','1','1','1','1','1'},{'1','1','1','1','1','1','1','0'},{'1','1','1','1','1','1','1','0'},{'1','1','1','1','1','0','0','0'},{'0','1','1','1','1','0','0','0'}};
        int i = new LeetCode221_MaximalSquare().maximalSquare(matrix);

        System.out.println("i = " + i);
    }

}
